#include <stdio.h>
#include <stdlib.h>
#include "BST.h"


int BSTInit(BST* tree) {
	tree->root = NULL;
	return 0;
}


int BSTInsert(BST* tree, ElemType data) {
	BSTNode* newNode = malloc(sizeof(BSTNode));
	if (newNode == NULL) {
		return 1;
	}
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	if (tree->root == NULL) {
		tree->root = newNode;
		return 0;
	}
	else {
		BSTNode* node = tree->root;
		for (; ; ) {
			if (data < node->data) {
				if (node->left == NULL) {
					node->left = newNode;
					return 0;
				}
				else {
					node = node->left;
				}
			}
			else if (data > node->data) {
				if (node->right == NULL) {
					node->right = newNode;
					return 0;
				}
				else {
					node = node->right;
				}
			}
			else {  // data == node->data
				free(newNode);  // Not inserted.
				return 2;
			}
		}
	}
}


int BSTPrintCore(BSTNode* root, int idle[], int idx) {
	if (root->left != NULL) {
		idle[idx] = 3;
		int bk;
		if (idx > 0) {
			bk = idle[idx-1];
			if (idle[idx-1] == 3){
				idle[idx-1] = 1;
			}
			if (idle[idx-1] == 4) {
				idle[idx-1] = 2;
			}
		}
		BSTPrintCore(root->left, idle, idx+1);
		if (idx > 0) {
			idle[idx-1] = bk;
		}
	}
	for (int x = 0; x < idx; x += 1) {
		if (idle[x] == 1) {
			printf("    ");
		}
		else if (idle[x] == 2) {
			printf("  │ ");
		}
		else if (idle[x] == 3) {
			printf("  ┌─");
		}
		else if (idle[x] == 4) {
			printf("  └─");
		}
	}
	printf("%d\n", root->data);
	if (root->right != NULL) {
		idle[idx] = 4;
		int bk;
		if (idx > 0) {
			if (idle[idx-1] == 3){
				idle[idx-1] = 2;
			}
			if (idle[idx-1] == 4) {
				idle[idx-1] = 1;
			}
		}
		BSTPrintCore(root->right, idle, idx+1);
		if (idx > 0) {
			idle[idx-1] = bk;
		}
	}
	return 0;
}


int BSTPrint(BSTNode* root) {
	if (root == NULL) {
		return 1;
	}
	int idle[1000];
	for (int idx = 0; idx < 100; idx += 1) {
		idle[idx] = 0;
	}
	return BSTPrintCore(root, idle, 0);
}


int BSTDetailCore(BSTNode* root) {
	if (root == NULL) {
		return 1;
	}
	else {
		printf("%-25p %-15d %-25p %-25p\n",
		       root, root->data, root->left, root->right);
		BSTDetailCore(root->left);
		BSTDetailCore(root->right);
		return 0;
	}
}


int BSTDetail(BSTNode* root) {
	printf("%-25s %-15s %-25s %-25s\n",
	       "Address", "Data", "Left", "Right");
	return BSTDetailCore(root);
}


BSTNode* BSTLocate(BSTNode* root, ElemType data) {
	BSTNode* node = root;
	while (node != NULL && data != node->data) {
		if (data < node->data) {
			node = node->left;
		}
		else {
			node = node->right;
		}
	}
	return node;
}


BSTNode* BSTParentOf(BSTNode* root, ElemType data) {
	BSTNode* parent = NULL;
	BSTNode* node = root;
	while (node != NULL && data != node->data) {
		if (data < node->data) {
			parent = node;
			node = node->left;
		}
		else {
			parent = node;
			node = node->right;
		}
	}
	if (node == NULL) {
		return NULL;
	}
	return parent;
}


BSTNode** BSTPointerOf(BST* tree, ElemType data) {
	BSTNode** target = &(tree->root);
	while (*target != NULL && data != (*target)->data) {
		if (data < (*target)->data) {
			target = &((*target)->left);
		}
		else {
			target = &((*target)->right);
		}
	}
	return target;
}


BSTNode* BSTLocateMin(BSTNode* root) {
	BSTNode* node = root;
	for (; node->left != NULL; node = node->left) {}
	return node;
}


ElemType BSTMin(BSTNode* root) {
	BSTNode* min = BSTLocateMin(root);
	return min->data;
}


BSTNode* BSTLocateMax(BSTNode* root) {
	BSTNode* node = root;
	for (; node->right != NULL; node = node->right) {}
	return node;
}


ElemType BSTMax(BSTNode* root) {
	BSTNode* max = BSTLocateMax(root);
	return max->data;
}


int BSTRemove(BST* tree, ElemType data) {
	BSTNode** target = BSTPointerOf(tree, data);
	if (*target == NULL) {  // Data node isn't in tree.
		return 1;
	}
	if ((*target)->left == NULL) {  // No left sub-tree.
		BSTNode* right = (*target)->right;
		free(*target);
		*target = right;
		return 0;
	}
	else if ((*target)->left->right == NULL) {
		BSTNode* max = (*target)->left;
		max->right = (*target)->right;
		free(*target);
		*target = max;
		return 0;
	}
	else {
		BSTNode* maxParent = (*target)->left;
		for (; maxParent->right->right != NULL; maxParent = maxParent->right) {}
		BSTNode* max = maxParent->right;
		maxParent->right = max->left;
		max->left = (*target)->left;
		max->right = (*target)->right;
		free(*target);
		*target = max;
		return 0;
	}
}


int main() {
	BST tree;
	BSTInit(&tree);

	int arr[] = {45, 66, 12, 22, 68, 3, 23, 87, 26, 18, 14, 69, 33, 99, 67, 87, 82, 82};
	for (int idx = 0; idx < sizeof(arr) / sizeof(int); idx += 1) {
		BSTInsert(&tree, arr[idx]);
		// BSTPrint(tree.root);
		// printf("----------\n");
	}
	BSTPrint(tree.root);
	BSTDetail(tree.root);

	printf("Min: %d   Max: %d\n", BSTMin(tree.root), BSTMax(tree.root));
	printf("Address of 67 is %p\n", BSTLocate(tree.root, 67));
	printf(" Parent of 67 is %p\n", BSTParentOf(tree.root, 67));

	for (int idx = 0; idx < sizeof(arr) / sizeof(int); idx += 1) {
		printf("Remove: %d\n", arr[idx]);
		BSTRemove(&tree, arr[idx]);
		BSTPrint(tree.root);
		printf("----------\n");
	}

	return 0;
}
